package aSortModel;

public class Quick_sort {
    /**
     * 快速排序
     * @param s 数组
     * @param l 左边界
     * @param r 右边界
     */
    void quick_sort(int s[], int l, int r) {
        if (l < r) {
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换
            int i = l, j = r, x = s[l];

            while (i < j) {
                // 从右向左找第一个小于x的数
                while(i < j && s[j] >= x)
                    j--;
                if(i < j)
                    s[i++] = s[j];

                // 从左向右找第一个大于等于x的数
                while(i < j && s[i] < x)
                    i++;
                if(i < j)
                    s[j--] = s[i];
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用
            quick_sort(s, i + 1, r);
        }
    }
    void sort(int s[],int l,int r){
        if(l<r){
            int i = l,j = r,x = s[i];
            while (i<j){
                //右向左找小于x的数
                while (i<j&&s[j]>=x){
                    j--;
                }
                s[i++] = s[j];
                //左向右找大于x的数
                while (i<j&&s[i]<x){
                    i++;
                }
                s[j--] = s[i];

            }
            s[i] = x;
            sort(s,l,i-1);
            sort(s,i+1,r);
        }

    }
}
